//题目:
// 给定一个整数数组 arr，返回所有 arr 的非空子数组的不同按位或的数量。
// 子数组的按位或是子数组中每个整数的按位或。含有一个整数的子数组的按位或就是该整数。
// 子数组 是数组内连续的非空元素序列。

// 示例 1：
// 输入：arr = [0]
// 输出：1
// 解释：
// 只有一个可能的结果 0 。

// 示例 2：
// 输入：arr = [1,1,2]
// 输出：3
// 解释：
// 可能的子数组为 [1]，[1]，[2]，[1, 1]，[1, 2]，[1, 1, 2]。
// 产生的结果为 1，1，2，1，3，3 。
// 有三个唯一值，所以答案是 3 。

// 示例 3：
// 输入：arr = [1,2,4]
// 输出：6
// 解释：
// 可能的结果是 1，2，3，4，6，以及 7 。

// 提示：
// 1 <= nums.length <= 5 * 104
// 0 <= nums[i] <= 109
#include<iostream>
#include<vector>
#include<set>
using namespace std;
//代码
class Solution 
{
public:
    int subarrayBitwiseORs(vector<int>& arr) 
    {
        int n=arr.size();
        //1.创建dp表————dp[i]表示:以arr[i]为结尾的子数组按位或的所有值
        vector<set<int>> dp(n);
        //2.初始化
        dp[0].insert(arr[0]);
        //3.填表————动态转移方程：dp[i]=nums[i]|dp[i-1]
        set<int> ret(dp[0]);
        for(int i=1;i<n;i++)
        {
            dp[i].insert(arr[i]);
            ret.insert(arr[i]);
            for(auto x:dp[i-1])
            {
                dp[i].insert(x|arr[i]);
                ret.insert(x|arr[i]);
            }
        }
        //4.确定返回值
        return ret.size();
    }
};